Remove all adjacent duplicates in string II¶
Time: O(N); Space: O(N); medium
Given a string s, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them causing the left and the right side of the deleted substring to concatenate together.
We repeatedly make k duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made.
It is guaranteed that the answer is unique.
Example 1:
Input: s = “abcd”, k = 2
Output: “abcd”
Explanation:
There’s nothing to delete.
Example 2:
Input: s = “deeedbbcccbdaa”, k = 3
Output: “aa”
Explanation:
First delete “eee” and “ccc”, get “ddbbbdaa”
Then delete “bbb”, get “dddaa”
Finally delete “ddd”, get “aa”
Example 3:
Input: s = “pbbcggttciiippooaais”, k = 2
Output: “ps”
Constraints:
1 <= len(s) <= 10^5
2 <= k <= 10^4
s only contains lower case English letters.
Hints:
Use a stack to store the characters, when there are k same characters, delete them.
To make it more efficient, use a pair to store the value and the count of each character.
[1]:
class Solution1(object):
def removeDuplicates(self, s, k):
"""
:type s: str
:type k: int
:rtype: str
"""
stk = [['^', 0]]
for c in s:
if stk[-1][0] == c:
stk[-1][1] += 1
if stk[-1][1] == k:
stk.pop()
else:
stk.append([c, 1])
return "".join(c*k for c, k in stk)
[2]:
sol = Solution1()
s = "abcd"
k = 2
assert sol.removeDuplicates(s, k) == "abcd"
s = "deeedbbcccbdaa"
k = 3
assert sol.removeDuplicates(s, k) == "aa"
s = "pbbcggttciiippooaais"
k = 2
assert sol.removeDuplicates(s, k) == "ps"